#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <climits>

using namespace std;

// 搜索旋转排序数组
class Solution
{
public:
    int search(vector<int> &nums, int target)
    {
        int left = 0, right = nums.size() - 1;
        while (left <= right)
        {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] == target)
                return mid;
            if (nums[0] < nums[mid])
            {
                if (nums[0] <= target && target < nums[mid])
                    right = mid - 1;
                else
                    left = mid + 1;
            }
            else
            {
                if (nums[mid] < target && target <= nums[nums.size() - 1])
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }
        return -1;
    }
};

// 寻找旋转排序数组中的最小值
class Solution
{
public:
    int findMin(vector<int> &nums)
    {
        int n = nums.size(), left = 0, right = n - 1;
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[n - 1])
                left = mid + 1;
            else
                right = mid;
        }
        return nums[left];
    }
};

// 寻找两个正序数组的中位数
class Solution
{
public:
    double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2)
    {
        vector<int> v(nums1.begin(), nums1.end());
        for (auto x : nums2)
        {
            v.push_back(x);
        }
        sort(v.begin(), v.end());
        int n = v.size();
        if (n % 2)
            return v[n / 2] * 1.0;
        else
            return (v[n / 2] + v[n / 2 - 1]) / 2.0;
    }
};

// 前缀树
struct Node
{
    bool isEnd;
    struct Node *next[26];
};
class Trie
{
public:
    Trie()
    {
        root = new Node();
    }

    void insert(string word)
    {
        struct Node *cur = root;
        int n = word.size();
        for (int i = 0; i < n; i++)
        {
            int index = word[i] - 'a';
            // 插入节点先看看当前node是否已经有指向该字母的next指针
            // 如果没有则新建一个节点
            if (cur->next[index] == nullptr)
            {
                cur->next[index] = new Node();
            }

            cur = cur->next[index];
            if (i == n - 1)
            {
                cur->isEnd = true;
            }
        }
    }

    bool search(string word)
    {
        int n = word.size();
        struct Node *cur = root;
        for (int i = 0; i < n; i++)
        {
            int index = word[i] - 'a';
            if (cur->next[index] == nullptr)
                return false;
            else
            {
                cur = cur->next[index];
                if (i == n - 1 && cur->isEnd)
                    return true;
                else if (i == n - 1)
                    return false;
            }
        }
        return false;
    }

    bool startsWith(string prefix)
    {
        int n = prefix.size();
        struct Node *cur = root;
        for (int i = 0; i < n; i++)
        {
            int index = prefix[i] - 'a';
            if (cur->next[index] == nullptr)
                return false;
            if (i == n - 1)
                return true;
            cur = cur->next[index];
        }
        return false;
    }

private:
    struct Node *root;
};
